package 链表1;

import java.util.LinkedList;

public class SinglyLinkedList<E> {
    //用来指向头节点，避免无人指向导致丢失
    private Node head;
    //用来指向尾巴节点
    private Node tail;
    //记录节点个数
    private int count;
    class Node{
        private int value;
        private Node next;

        public Node(int value) {
            this.value = value;
        }
    }
    public void create(){
        Node node1=new Node(12);
        Node node2=new Node(12);
        Node node3=new Node(12);
        Node node4=new Node(12);
        head=node1;
        node1.next=node2;
        node2.next=node3;
        node3.next=node4;
        tail=node4;
        count=4;
    }
    //得到单链表的长度  如果每次调用他都遍历一遍太慢了
    public int size(){
        return count;
    };
    //打印链表
    public void display(){
        Node cur=this.head;
        while (cur!=null){
            System.out.print(cur.value+" ");
            cur=cur.next;
        }
        System.out.println();
    };
    //头插法
    public void addFirst(int data){
        Node node=new Node(data);
        node.next=head;
        head=node;
        count++;
    };
    //尾插法
    public void addLast(int data){
        Node node=new Node(data);
        if(head==null){
            head=node;
            tail=node;
        }else {
            tail.next=node;
            tail=node;
            count++;
        }
    };
    //检查index是否合法
    private void IndexLegal(int index){
        if(index<0||index>=count){
            throw new IndexOutOfBoundsException("index不合法！");
        }
    }
    //寻找index位置的上一个节点
    private Node findIndexSubOfOne(int index) {
        Node cur = head;
        while (index-1 != 0) {
            cur = cur.next;
            index--;
        }
        return cur;
    }
    //任意位置插入,第一个数据节点为0号下标
    public boolean addIndex(int index,int data){
        if(index==0){
            addFirst(data);
            return true;
        }else if(count==index){
            addLast(data);
            return true;
        }else {
            try{
                IndexLegal(index);
                //合法了
                Node node=new Node(data);//插入的节点
                Node cur=findIndexSubOfOne(index);//找到index位置的上一个节点
                //进行插入
                node.next=cur.next;
                cur.next=node;
                count++;
                return true;
            }catch (IndexOutOfBoundsException e){
                e.printStackTrace();
            }
        }
        return false;//插入失败
    };
    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key){
        Node cur=head;
        while (cur!=null){
            if(cur.value==key){
                return true;
            }
            cur=cur.next;
        }
        return false;
    };

    //删除第一次出现关键字为key的节点
    public void remove(int key) {
        Node cur = head;
        //key在头结点
        if (key == head.value) {
            head = head.next;
            count--;
        } else {
            while (cur.next != null) {
                if (cur.next.value == key) {
                    //第一个key在尾巴节点
                    if (cur.next.next == null) {
                        cur.next = null;
                        tail = cur;
                        count--;
                        break;
                    }
                    //key在其他位置
                    cur.next = cur.next.next;
                    count--;
                    break;
                }
                cur = cur.next;
            }

        }
    };

    //删除所有值为key的节点
    public void removeAllKey(int key) {
        //如果头节点是key，单独讨论
        while (head!=null&&head.value==key){
            head=head.next;
            count--;
        }
        //key在其他节点
        if(head!=null){
            Node pre=head;
            Node cur=head.next;
            while (cur!=null){
                if(cur.value==key){
                    pre.next=cur.next;
                    count--;
                }else {
                    pre=cur;
                }
                cur=cur.next;
            }
        }
    };

    public void clear(){
        Node cur=head;
        head=null;
        tail=null;
        while (cur!=null){
            Node tmp=cur.next;
            cur.next=null;
            cur=tmp;
        }
        count=0;
    };
}
